home *** CD-ROM | disk | FTP | other *** search
- .sh 1 "INTRODUCTION"
- .pp
- Relational database management systems are widely available in the
- commercial market.
- Currently available systems run on a variety of hardware, ranging from
- DEC minicomputers (e.g., Informix, Oracle, Unify) to IBM mainframes
- (e.g., Adabas, Datacom/DB, DB2, IDMS/R).
- These systems have been successful because of the merits of
- the relational model, as first illustrated by
- two research prototypes, INGRES [STON76]
- and SYSTEM-R [ASTR76].
- INGRES and SYSTEM-R not only illustrated the feasibility of
- the relational model, but their respective query languages,
- QUEL [HELD75b] and SQL [CHAM76], also
- showed that it is possible to ask queries without explicitly
- specifying access paths.
- The ability to support these non-procedural query languages is a result of
- sophisticated query optimization algorithms.
- INGRES introduced a technique known as query decomposition [WONG76],
- while SYSTEM-R employed an exhaustive search algorithm [SELI79].
- Largely due to the success of these algorithms, relational systems were made
- efficient.
- Therefore, coupled with the simplicity and uniformity of the
- relational model, it
- is not surprising that relational databases have established a
- formidable presence in the commercial market.
- .pp
- The relational model, however, has been criticized for its impoverished
- semantics [KENT79], [ZANI83] and inability to provide strong support
- for non-business applications [HASK82].
- In recent years, researchers have been investigating the possibility of
- extending query languages in relational systems to support new application
- areas as well as better semantics.
- Examples include:
- .ip "\(bu"
- a proposal to support abstract data types (ADTs) and operators
- in INGRES to improve the semantics of applications [FOGG82], [ONG82]
- .ip "\(bu"
- a new language, QUEL*, to support the transitive
- closure operations required in artificial intelligence applications [KUNG84]
- .ip "\(bu"
- a proposal to support QUEL as a data type
- to increase the data modeling power of relational systems [STON84], [STON85b]
- .ip "\(bu"
- a proposal to support rules and triggers in a relational system to
- provide inference and forward chaining needed in
- expert system applications [STON85a].
- .lp
- .pp
- The ideas behind these proposals are being incorporated into POSTGRES
- (\*(lqPOSTinGRES\*(rq),
- a next-generation relational database system being built at
- the University of California, Berkeley [STON86b].
- Providing better support for engineering design and artificial intelligence
- applications are among the goals of POSTGRES.
- To meet these goals, POSTGRES will support extendible and user-defined
- access methods [STON86a] as well as abstract data types, transitive
- closure queries, procedural data fields, triggers, and rules.
- The query language for the system will be called \*(lqPOSTQUEL.\*(rq
- .pp
- POSTGRES is still in its preliminary implementation phase.
- However, a query optimizer for the system has been built.
- Although the basic optimization algorithm is modeled after the SYSTEM-R
- approach, there are many other issues that the optimizer must
- contend with given the novel features of POSTGRES.
- Section 2 will introduce these features.
- Section 3 will then discuss design decisions that were made in formulating
- optimization algorithms.
- Section 4 will discuss implementation decisions made, and finally
- section 5 will evaluate the performance of the POSTGRES optimizer by comparing
- it with the query optimizer of another relational system.
-